package leetcode_100;

/**
 *@author 周杨
 *MaximumSubarray_53 最大连续数组问题
 *describe: 用动态规划记录  时间复杂度O(N) AC 82%
 *2018年5月6日 下午3:56:22
 */
public class MaximumSubarray_53 {
	int res;
	public static void main(String[] args) {
		MaximumSubarray_53 test=new MaximumSubarray_53();
		int nums[]=new int[] {-2,1,-3,4,-1,2,1,-5,4};
		System.out.println(test.maxSubArray(nums));

	}
	public int maxSubArray(int[] nums) {
		int continueHelp=0;
		int max=Integer.MIN_VALUE;
		for(int i=0;i<nums.length;++i) {
			continueHelp=continueHelp>0?continueHelp+nums[i]:nums[i];//更新当前的最大连续数组
			max=max>continueHelp?max:continueHelp;//最大值要么是以前的最大值 要么是当前最大连续数组的总值
		}
        return max;
    }

}
